A network switch of a data communications network provides a "switching function" for transferring information, such as data frames, among entities of the network. Typically, the switch is a computer comprising a collection of components (e.g., cards) interconnected by a backplane of wires. Each card may include a limited number of ports that couple the switch to the other network entities over various types of media, such Ethernet, FDDI or token ring connections. A network entity may consist of any device that "sources" (i.e., transmits) or "sinks" (i.e., receives) data frames over such media.
The switching function provided by the switch typically comprises receiving data at a source port from a network entity, transferring the data over the backplane to a destination port and, thereafter, transmitting that data over a medium to another entity of the network. In order for the data to be transferred, the switch may include a forwarding engine and associated address translation mechanism. An example of such an address translation mechanism is described in U.S. Pat. No. 5,740,171, issued Apr. 14, 1998, entitled ADDRESS TRANSLATION MECHANISM FOR A HIGH PERFORMANCE NETWORK SWITCH, which is commonly owned by the assignee of the present invention. The address translation mechanism described therein quickly and efficiently renders forwarding decisions for data frames transported among ports of a high-performance switch on the basis of, inter alia, virtual local area network (VLAN) associations among the ports.
The translation mechanism comprises a plurality of forwarding tables, each of which contains entries having unique index values that translate to selection signals for ports destined to receive the data frames. Each port is associated with a unique index value and a VLAN identifier to facilitate data transfers within the switch at accelerated speeds and addressing capabilities.
As described in the patent, a media access control (MAC) address is combined with the VLAN identifier to produce a base line numerical quantity for searching the forwarding tables. Each table entry is directly accessed, however, by a key comprising a hash transformation of this MAC/VLAN quantity. A comparison circuit arrangement of is the mechanism is also provided to validate the forwarding table entry mapped by the hashed MAC/VLAN quantity. That is, the circuit arrangement compares the base line numerical quantity to a MAC/VLAN value stored in the mapped entry to ensure that the entry contains the correct index value. If the compared items match, the index value stored in the table is provided to a target logic circuit for translation to a signal that selects a port or group of ports for receiving the data frame. If the items do not match, the VLAN identifier is passed to the target logic circuit with the result that all ports having that VLAN identifier receive the frame in accordance with a multicast transfer.
The hash function used to find the index value maps a large address space with a much smaller address space. In doing so, however, aliasing can occur in that more than one key, for example, a MAC address/VLAN pair, can hash to the same table entry. One solution to this limitation has been to provide a hash table comprising several pages which can be used as alternates when a particular key (e.g., MAC address/VLAN pair) hashes to the same table entry. For example, a first MAC address/VLAN pair may hash to a particular table entry in which case that entry (or line) corresponding to the first page of the table is thereafter associated with that MAC address/VLAN pair. If a second MAC address/VLAN pair hashes to the same value, thus pointing to that same entry, then it is stored in the corresponding entry on the second page of the table.
The problem with this type of paging scheme, however, is that it increases the overall table access time because the hash transformation may not always result in a "hit" on the first page accessed. Specifically, after the hashed address is calculated, it is used to point to the entry (or line) to access, but the look up always begins on the first page. If a match is not found, the corresponding entry on the second page is checked, and if there is no match this procedure continue s through all the pages of the table until a match is realized. In such conventional systems, the order in which pages are accessed, including which page is accessed first, is the same for all hashed addresses. But, serially checking the various pages consumes time, perhaps on the order of several cycles. Optimum performance, namely highest speed, is achieved when the desired entry is found on the first page checked.
Therefore, it is among the objects of the present invention to provide a mechanism for high-speed look up of hash table information needed for rendering forwarding decisions in a network switch.
Another object of the present invention is to provide a hashing technique which increases the likelihood of accessing desired data upon a first look up of a hash table.
It is a further object of the present invention to provide a mechanism that efficiently implements "port-based" VLAN association operations within a high-performance network switch.